package 剑指II;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-12-14
 **/

public class Jz094最少回文分割 {

    /**
     * 给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。
     * 返回符合要求的 最少分割次数 。
     * <p>
     * 示例 1：
     * 输入：s = "aab"
     * 输出：1
     * 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
     * 示例 2：
     * 输入：s = "a"
     * 输出：0
     * 示例 3：
     * 输入：s = "ab"
     * 输出：1
     *  
     * 提示：
     * 1 <= s.length <= 2000
     * s 仅由小写英文字母组成
     */

    public int minCut(String s) {

        char[] arr = s.toCharArray();
        boolean[][] dp = new boolean[s.length()][s.length()];

        for (int i = 0; i < dp.length; i++) {
            // 当前一个字符必定是回文串
            dp[i][i] = true;
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] == arr[i] && (j - i < 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                }
            }
        }

        int[] resultDp = new int[arr.length];
        resultDp[0] = 0;
        // 继续从1到length

        for (int i = 1; i < arr.length; i++) {
            resultDp[i] = resultDp[i - 1] + 1;
            if (dp[0][i]) {
                resultDp[i] = 0;
                continue;
            }
            for (int j = 1; j < i; j++) {
                if (dp[j][i]) {
                    // 最优前部分 + 后面整段
                    resultDp[i] = Math.min(resultDp[i], resultDp[j - 1] + 1);
                }
            }
        }

        return resultDp[arr.length - 1];
    }

    public static void main(String[] args) {
        Jz094最少回文分割 n = new Jz094最少回文分割();
        int result = n.minCut("abb");
        System.out.println(result);
    }

}
